An owner of a database or data store of information may want to provide a mechanism to allow a requester to determine whether a piece of information is contained in the database without the requester having access to all of the owner's data and without the owner having knowledge of the content of the request. The privacy concern of the requester may be based on the sensitivity of the query, organizational goals, or privacy requirements encumbering the data.
For example, a requester may operate a web site that collects customer information, such as email addresses as a part of its normal operating procedure. The privacy terms of the web site may state that it will not share customer information. A database owner may collect and provide a database of email addresses of people who have previously shown interest in receiving a particular type of product information. The requester may want to compare its customer email addresses with the data owner's database to explore marketing opportunities for its customers, but according to the terms of the website, it cannot reveal the email addresses of its customers.
In one solution to this problem, the data owner may publish the database to a shared location or send the entire database to the requester. The requester may then run a query against the data store. One problem with this approach is that it may require the data owner to release its data store to a publishing point or to the requester. The data owner may prefer (or be under an obligation) that the data store remain private. Such a query may also still violate the terms under which the requester may release its customers' email addresses. Therefore, a mechanism is needed that can both preserve the privacy of the information sought and the privacy of the information held.
In addition, the data owner may wish to provide related data to the requester. In the example above, the data owner may also have collected demographic data associated with the email addresses. This additional data may be transmitted to the requester when the requested record is found in the database. But because the data request is private, a mechanism is needed to transmit the data to the requester without the data owner learning what information was requested. In addition, the data owner needs a way to maintain the privacy of the related data.
Therefore, a method and system is desired that can provide, as part of a query against a database, a way of preserving privacy during querying operation such that the requester only learns the specific information requested and the data owner does not learn the content of the request. The following disclosure solves these problems. As described in detail below, it is noted that this disclosure applies to all types of data requests and database types.